最小生成树算法

1. 基本概念

在理解最小生成树之前，需要先明白几个图论的基本概念：

图 (Graph)：由顶点（Vertex）和边（Edge）组成的数据结构。
无向图 (Undirected Graph)：边没有方向，(A, B) 和 (B, A)是同一条边。
连通图 (Connected Graph)：图中任意两个顶点之间都至少存在一条路径。
权值 (Weight)：赋给每条边的数值，可以代表成本、距离、时间等。
生成树 (Spanning Tree)：对于一个连通图，一个生成树是它的一个子图，这个子图需要满足两个条件：
1. 包含原图中所有的顶点。
2. 它本身是一棵树（即，它没有环路，并且是连通的）。
- 对于一个有 V 个顶点的图，其任何一棵生成树都有且仅有 V-1 条边。

最小生成树 (Minimum Spanning Tree, MST)

对于一个带权的、无向的、连通的图，最小生成树是它众多生成树中，所有边的权值之和最小的那一棵。

简单比喻：想象一下，有 V 个城市，你需要在这些城市之间铺设光缆，使得所有城市都能相互通信。每两个城市之间铺设光缆的成本（权值）是已知的。你的任务是找到一个铺设方案，用最低的总成本连接所有城市。这个最低成本的方案，就是该图的最小生成树。

2. 核心理论：切割性质 (Cut Property)

Prim 和 Kruskal 算法都属于贪心算法。它们之所以能够正确地找到全局最优解（MST），是基于一个非常重要的理论——切割性质。

切割 (Cut)：将图的所有顶点分成两个不相交的集合 S 和 T。
横切边 (Crossing Edge)：一端在集合 S，另一端在集合 T 的边。

切割性质内容：

对于图的任意一个切割 (S, T)，在所有横切边中，权值最小的那条边必定属于该图的某一个最小生成树。

简单证明（反证法）：假设权值最小的横切边 e 不在任何一个 MST 中。我们任意取一个 MST，记为 T_mst。

由于 T_mst 连接了所有顶点，所以必然存在另一条横切边 e' 在 T_mst 中，连接着集合 S 和 T。
根据我们的假设，weight(e) < weight(e')。
现在，我们在 T_mst 中加入边 e。此时，图中会形成一个环路，这个环路必然同时包含了 e 和 e'。
我们从这个环路中移除边 e'。这样，图重新变回一棵树（V个顶点，V-1条边），并且仍然连接所有顶点，所以它是一棵新的生成树。
这棵新生成树的总权值为 Sum(T_mst) - weight(e') + weight(e)。因为 weight(e) < weight(e')，所以新树的总权值比原来的 T_mst 还要小。
这与 T_mst 是最小生成树的假设相矛盾。因此，我们最初的假设（“权值最小的横切边 e 不在任何 MST 中”）是错误的。

这个性质是两个贪心算法的理论基石。它们每一步的选择，都是在某个切割中选择了那条最小的横切边。

3. 两大经典算法

A. Prim (普里姆) 算法

核心思想：从任意一个顶点开始，逐步“生长”出一棵树。每一步都选择连接已在树中的顶点与未在树中的顶点的边中，权值最小的那一条，并将其对应的顶点和边加入树中，直到所有顶点都被包含。

这完美地应用了切割性质：S = {已在树中的顶点}，T = {未在树中的顶点}。Prim 算法每一步都选择最小的横切边。

算法步骤：

初始化：
- 创建一个集合 U，用于存放已加入 MST 的顶点。首先将任意一个起始顶点 s 放入 U。
- 创建一个“距离”数组 dist，dist[i] 记录顶点 i 到集合 U 的最短边的权值。初始化 dist[s] = 0，其他顶点的 dist 值为无穷大（∞）。
循环 V-1 次（因为要找 V-1 条边）： a. 在所有不属于 U 的顶点中，找到 dist 值最小的顶点 u。 b. 将顶点 u 加入集合 U。 c. 将连接 u 和 U 的那条最短边加入 MST。 d. 更新：对于顶点 u 的所有邻居 v，如果 v 不在 U 中，并且边 (u, v) 的权值小于当前的 dist[v]，则更新 dist[v] 的值为 weight(u, v)。
循环结束后，就得到了 MST。

实现与复杂度：

邻接矩阵 + 暴力搜索：
- 存储图：用邻接矩阵。
- 找 dist 最小的顶点：每次需要 O(V) 的时间遍历 dist 数组。
- 总复杂度：V 次循环 × O(V) 查找 = O(V²)。适用于稠密图（边的数量接近 V²）。
邻接表 + 优先队列 (二叉堆)：
- 存储图：用邻接表。
- dist 数组的功能由优先队列实现。每次从队列中取出 dist 最小的顶点，时间为 O(logV)。
- 更新邻居的 dist 值（decrease-key 操作），时间为 O(logV)。
- 总复杂度：O(E logV)。适用于稀疏图（边的数量远小于 V²）。

Python 示例 (邻接矩阵版)


import sys
 
class PrimMST:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]
 
    def find_mst(self):
        # 存储MST的父节点关系
        parent = [-1] * self.V 
        # 存储顶点的dist值
        key = [sys.maxsize] * self.V 
        # 记录顶点是否已包含在MST中
        mst_set = [False] * self.V
 
        # 从顶点0开始
        key[0] = 0
        parent[0] = -1 # 第一个节点没有父节点
 
        for _ in range(self.V):
            # 1. 在未处理的顶点中找到key值最小的顶点u
            min_key = sys.maxsize
            u = -1
            for v in range(self.V):
                if not mst_set[v] and key[v] < min_key:
                    min_key = key[v]
                    u = v
            
            if u == -1: continue # 以防图不连通
 
            # 2. 将顶点u加入MST集合
            mst_set[u] = True
 
            # 3. 更新u的邻居的key值和parent
            for v in range(self.V):
                # graph[u][v] > 0 表示存在边
                # mst_set[v] is False 表示v还未加入MST
                # key[v] > self.graph[u][v] 表示找到了更短的边
                if self.graph[u][v] > 0 and not mst_set[v] and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u
 
        # 打印MST
        print("边 \t权值")
        for i in range(1, self.V):
            print(f"{parent[i]} - {i}\t{self.graph[i][parent[i]]}")
 
# 使用示例
g = PrimMST(5)
g.graph = [[0, 2, 0, 6, 0],
           [2, 0, 3, 8, 5],
           [0, 3, 0, 0, 7],
           [6, 8, 0, 0, 9],
           [0, 5, 7, 9, 0]]
g.find_mst()

B. Kruskal (克鲁斯卡尔) 算法

核心思想：将所有边按权值从小到大排序，然后从最小的边开始，依次考察每一条边。如果这条边连接的两个顶点当前不属于同一个连通分量（即加入这条边不会形成环路），则将这条边加入 MST。重复此过程，直到加入了 V-1 条边。

算法步骤：

初始化：
- 创建一个集合用于存放 MST 的边，初始为空。
- 将图中所有的边存入一个列表，并按权值从小到大排序。
- 创建一个并查集 (Disjoint Set Union, DSU) 数据结构，其中每个顶点初始时都自成一个集合。
遍历排序后的边：
- 对于每条边 (u, v)，其权值为 w：
- 使用并查集的 find 操作，检查顶点 u 和 v 是否在同一个集合中。
  - 如果 find(u) != find(v)，说明它们不在一个连通分量里，加入这条边不会形成环路。
    - 将这条边 (u, v) 加入 MST 集合。
    - 使用并查集的 union 操作，合并 u 和 v 所在的集合。
  - 如果 find(u) == find(v)，说明它们已经连通，加入这条边会形成环路，因此跳过这条边。
当 MST 集合中的边数达到 V-1 时，算法结束。

实现与复杂度：

排序：对 E 条边进行排序，时间复杂度为 O(E logE)。
并查集操作：在路径压缩和按秩/大小合并的优化下，E 次 find 和 V-1 次 union 操作的均摊时间复杂度接近常数，总共约为 O(E α(V))，其中 α 是反阿克曼函数，增长极其缓慢，可视为常数。
总复杂度：主要由排序决定，即 O(E logE)。由于 E 通常小于 V²，所以 logE 通常小于 log(V²)=2logV，因此也可以写成 O(E logV)。

Python 示例 (带并查集)


class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
 
    def find(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.find(self.parent[i]) # 路径压缩
        return self.parent[i]
 
    def union(self, i, j):
        root_i = self.find(i)
        root_j = self.find(j)
        if root_i != root_j:
            # 按秩合并
            if self.rank[root_i] > self.rank[root_j]:
                self.parent[root_j] = root_i
            else:
                self.parent[root_i] = root_j
                if self.rank[root_i] == self.rank[root_j]:
                    self.rank[root_j] += 1
            return True
        return False
 
class KruskalMST:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [] # 存储边 (u, v, weight)
 
    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])
 
    def find_mst(self):
        result = []
        # 1. 按权值对所有边排序
        self.graph = sorted(self.graph, key=lambda item: item[2])
        
        dsu = DSU(self.V)
        edge_count = 0
        i = 0
 
        while edge_count < self.V - 1 and i < len(self.graph):
            u, v, w = self.graph[i]
            i += 1
            
            # 2. 如果加入这条边不形成环路，则加入
            if dsu.union(u, v):
                edge_count += 1
                result.append([u, v, w])
 
        # 打印MST
        print("边 \t权值")
        total_weight = 0
        for u, v, weight in result:
            print(f"{u} - {v}\t{weight}")
            total_weight += weight
        print(f"最小总权值: {total_weight}")
 
# 使用示例
g = KruskalMST(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
 
g.find_mst()

4. 算法对比：Prim vs. Kruskal

特性	Prim 算法	Kruskal 算法
核心策略	”加点法”：从一个点开始，不断将最近的点纳入集合。	“加边法”：按边的权重从小到大尝试，不构成环就加入。
数据结构	邻接矩阵/邻接表，通常配合优先队列优化。	边的列表，必须配合并查集。
过程	始终保持一个连通的树，不断扩大。	初始时是森林，不断将独立的树合并，最终形成一棵树。
复杂度	O(V²) 或 O(E logV)	O(E logE) 或 O(E logV)
适用场景	稠密图 (Dense Graph)，边数 E 接近 V²。此时 O(V²) 的 Prim 算法可能比 O(E logE) ≈ O(V² logV) 的 Kruskal 更优。	稀疏图 (Sparse Graph)，边数 E 远小于 V²。此时 O(E logE) 优于 O(V²)。
其他	算法过程类似 Dijkstra。	可以轻松处理不连通图，得到一个最小生成森林。

总结：在选择时，主要看图的密度。稀疏图用 Kruskal，稠密图用 Prim。

5. 实际应用

最小生成树算法在现实世界中有广泛的应用，主要用于解决以最低成本连接所有点的问题。

网络建设：
- 铺设电网、自来水管道、天然气管道，目标是用最短的总线路连接所有用户。
- 设计通信网络（如光纤、电话线），以最小成本连接所有城市或交换机。
交通网络：
- 规划公路或铁路网，在连接所有重要城镇的前提下，使总修建长度最短。
电路设计：
- 在电路板上连接各个引脚，需要使总的导线长度最短以减少材料成本和信号延迟。
聚类分析 (Clustering)：
- 在机器学习和数据挖掘中，可以将数据点视为顶点，点之间的距离视为权值。MST 可以帮助识别数据点之间的“骨架”结构，用于某些聚类算法。
近似算法：
- 解决一些 NP-hard 问题（如旅行商问题 TSP）时，MST 可以作为一个很好的近似解或解决过程中的一个步骤。例如，MST 的总权值是 TSP 最优路径长度的一个下界。